package ms.sudoku.technique;

import java.util.Arrays;
import java.util.Iterator;

//--------------------------------------------------------------------------
//
//  Copyright (c) Microsoft Corporation.  All rights reserved.
//
//  File: CombinationIterator.cs
//
//  Description: Allows for iteration through all combinations from an array.
//
//--------------------------------------------------------------------------
/**
 * An IEnumerable for combinations.
 */
public final class CombinationIterator implements Iterable<int[]> {
	public static void main(String[] args) {
		int[] nums = { 1, 2, 3, 4, 5 };
		int size = 3;
		for (int[] c : new CombinationIterator(size, nums)) {
			System.out.println(Arrays.toString(c));
		}
	}

	/**
	 * The current indices.
	 */
	private int[] _indices;
	/**
	 * The number K of items to choose.
	 */
	private int _size;
	/**
	 * The numbers to choose from.
	 */
	private int[] _numbers;

	/**
	 * Initializes the iterator.
	 * 
	 * @param size
	 *            The number of items to choose.
	 * @param numbers
	 *            The numbers from which to choose.
	 */
	public CombinationIterator(int size, int[] numbers) {
		_size = size;
		_numbers = numbers;
	}

	@Override
	public Iterator<int[]> iterator() {
		return new Iterator<int[]>() {
			boolean holding = false;
			boolean hasNext = false;

			@Override
			public boolean hasNext() {
				if (false == holding) {
					hasNext = moveNext();
					holding = true;
				}
				return hasNext;
			}

			@Override
			public int[] next() {
				holding = false;
				return getCurrent();
			}

			@Override
			public void remove() {
			}
		};
	}

	/**
	 * Resets the enumerator.
	 */
	public void reset() {
		_indices = null;
	}

	private int[] _result;

	/**
	 * Gets the current combination.
	 */
	public int[] getCurrent() {
		for (int i = 0; i < _indices.length; i++) {
			_result[i] = _numbers[_indices[i]];
		}
		return _result;
	}

	/**
	 * Moves to the next combination.
	 * 
	 * @return A value indicating if there are more combinations from which to
	 *         choose.
	 */
	public boolean moveNext() {
		if (_indices == null) {
			_indices = new int[_size];
			_result = new int[_size];
			for (int i = 0; i < _indices.length; i++)
				_indices[i] = i;
			return true;
		} else {
			if (_indices[0] >= _numbers.length - _size)
				return false;

			// Find the next position to be incremented
			int pos;
			for (pos = _indices.length - 1; pos > 0 && _indices[pos] == _numbers.length - _size + pos; pos--)
				;
			// Increment the position
			_indices[pos]++;
			for (int j = pos; j < _size - 1; j++)
				// Increment everything else
				_indices[j + 1] = _indices[j] + 1;
			return true;
		}
	}

}
